The present invention relates to optical modified signed-digit (MSD) arithmetic processing and specifically, to the use of an opto-electronic shared content-addressable memory processor in parallel MSD arithmetic computation. More specifically, MSD arithmetic operations (addition or subtraction of two N-bit numbers) is decomposed into a matrix-matrix multiplication step followed by a combination of a threshold and logic operations.
Addition is the most fundamental operation for any arithmetic computation. Other important arithmetic operations, such as subtraction, multiplication and division, can all be realized through additions together with logic operations. Optical computing will not become widespread until optical technology provides convincing evidence showing that basic arithmetic computations such as additions can be efficiently performed. Using a binary number system, addition speed is inevitably limited by the employed carry propagation scheme. Different methods of advancing carries have been proposed, which include the use of carry look-ahead and carry-save addition approaches. However, the sequential nature of the binary addition can not be fundamentally changed. Carry-limited or carry-free arithmetic operations using other number systems have long been investigated. While the residue number system can be used for carry-limited addition, subtraction, and multiplication directly, the so-called modified signed digit (MSD) number representation can be directly used for carry-limited addition and subtraction operations. A comparison of the two representations in terms of their similarity to the binary representations shows that the binary number representation is closer to the MSD than to the residue number system since the binary number representation is a subset of the MSD representation. The closer relationship makes it easier for a binary number to be processed in a MSD processor. The other often-mentioned advantage of the MSD over the residue representation is that the MSD uses one fixed module while the residue uses a set of different modules for computation, implying that the processing complexity of the former is evenly distributed throughout the physical system while that of the latter is asymmetrically distributed.
Based on the MSD number representation, architectures and algorithms have been proposed for fast arithmetic computations. A study of the trade-off between the processing complexity and the latency has shown that the carries generated during an addition of two MSD numbers can only propagate three steps before being compensated as illustrated in FIG. 1. In order to absorb the three steps time delay, it is also possible to design a single stage fully parallel MSD adder at the expense of using a more complicated system such as shown in FIG. 2. Three stages having a total of eleven two-variable logic gates within the dashed lines in FIG. 1 are compressed into a single stage of adders. Each of these stages of adders requires six variables to generate a single bit output. Various VLSI digital electronic as well as optical processing architectures have been proposed. Space-encoded electronic MSD gates are cascaded to form a parallel MSD adder which can then be used as a building block for other MSD arithmetic processors. Using this idea with optical processing methods has resulted in a number of optical MSD adder architectures. However, optics has not shown sufficient nonlinear processing flexibility and reliability to promote its application in the extremely competitive area of logic processing. An alternative to optical logic is the use of an optical memory look-up processor for the purpose of arithmetic processing. There, the results of the carry-limited parallel addition are recorded in either a location-addressable or a content-addressable memory (CAM). The numbers to be added are used either as the memory address directly or as special codes for access to the logically reduced associated memory in order to obtain the final addition result.
The MSD addition architecture in FIG. 2 can be used to build a CAM based MSD adder. When the electronic CAM technology is used, the generation of each bit of MSD addition result physically requires a programmable logic array (PLA) with a 1K switching capacity unless time multiplexing of the PLA is used which can save processing hardware at the cost of additional processing time.